﻿// 3409. 这是一棵树吗.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <set>



using namespace std;



/*
https://www.acwing.com/problem/content/3412/

树是一种众所周知的数据结构，它既可以是空的（null），也可以是一个节点或多个节点的集合，这些节点通过有向边连接且满足以下属性。

有且仅有一个节点，我们称之为根节点，没有任何有向边指向该节点。

除了根节点外，每个节点都有且仅有一条指向它的边。

从根节点到每个其他节点都有一条唯一的有向边序列。

例如，参考下图，节点用圆圈表示，有向边用带箭头的线表示，前两个图形是树，最后一个图形不是树。

1.png

给定若干个由有向边连接的节点集合的描述，请确定它们是否满足树的定义。

输入格式
输入包含多组测试数据。

每组数据占若干行，包含若干个对于有向边的描述，每个有向边的描述包含两个整数 a和 b
，表示这条有向边从节点 a 指向节点 b。

当出现数对 0 0 时，表示这组数据的输入结束。

当出现数对 -1 -1 时，表示全部输入结束。

具体可参考样例。

输出格式
每个数据输出占一行，表示结果。

格式为 Case k is a tree. 或 Case k is not a tree.，其中 k 为组别编号，从 1开始。

数据范围
0<a,b<10000,
每个输入最多包含 100组数据。

输入样例
6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0
-1 -1
输出样例：
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
*/

const int N = 10010;

int t;
int a, b, edgcnt,pointcnt;

int indeg[N];	//哈希点的入度
int f[N];
int pointhash[N];


void init() {
	for (int i = 0; i < N; i++) {
		f[i] = i;
	}
	t++; edgcnt = 0; pointcnt = 0;
	memset(pointhash,0,sizeof pointhash);
	memset(indeg, 0, sizeof indeg);
}

int find(int x) {
	if (x != f[x]) f[x] = find(f[x]);

	return f[x];
}

void merge(int a, int b) {
	a = find(a); b = find(b);
	if (a < b) {
		f[b] = a;
	}
	else {
		f[a] = b;
	}
}

void solve() {
	int zeroInCnt = 0;

	pointcnt = 0;
	for (int i = 1; i < N; i++) {
		if (pointhash[i] != 0)pointcnt++;
	}

	if ( 0== pointcnt) {
		printf("Case %d is a tree.\n",t);
		return;
	}

	int root = -1;
	for (int i = 1; i < N; i++) {
		if (pointhash[i] == 0) continue;
		int p = i;
		if (indeg[p] == 0) {
			zeroInCnt++;
		}
		else if (indeg[p] > 1) {
			printf("Case %d is not a tree.\n",t);
			return;
		}
		if (root == -1) {
			root = find(p);
		}
		else {
			root = find(root);
			if (root != find(p)) {
				printf("Case %d is not a tree.\n",t);
				return;
			}
		}
	}

	if (zeroInCnt == 1 && edgcnt == pointcnt - 1) {
		printf("Case %d is a tree.\n",t);
	}
	else {
		printf("Case %d is not a tree.\n",t);
	}
}



int main()
{
	init();
	while (scanf("%d%d",&a,&b)) {
		if (a == -1 || b == -1) break;
		if (a == 0 && b == 0) {
			solve();
			init();
		}

		if (a != 0 && b != 0) {
			edgcnt++;
			indeg[b]++;
			pointhash[a]++; pointhash[b]++;
			merge(a, b);
		}
	}

	return 0;
}

